{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 给定长度为`n`的列表，编写递归程序求其最大元素，并分析其时间复杂度和空间复杂度．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'\\n时间复杂度为O(n)\\n空间复杂度为O(1)\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findMax(A,i=0,j=0):\n",
    "    if i<len(A):\n",
    "        if A[j]<A[i]:\n",
    "            j=i;\n",
    "        return findMax(A,i+1,j);\n",
    "    elif i==len(A):\n",
    "        return print(A[j]);\n",
    "    else:\n",
    "        return print('A IS EMPTY!');\n",
    "\n",
    "if __name__=='__main__':\n",
    "    A =[1,4,7,2,5,8,3,6,9];\n",
    "    findMax(A);\n",
    "    \n",
    "'''\n",
    "时间复杂度为O(n)\n",
    "空间复杂度为O(1)\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 编写递归函数计算`n`阶调和数(Harmonic number):\n",
    "$$\n",
    "H_n = \\sum_{i=1}^n \\frac1i\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5\n",
      "2.283333333333333\n"
     ]
    }
   ],
   "source": [
    "def harmonicNum(n):\n",
    "    if n==1:\n",
    "        return 1;\n",
    "    else:\n",
    "        return harmonicNum(n-1)+1/n;\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    print(harmonicNum(2))\n",
    "    print(harmonicNum(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 编写递归函数，将表示整数的字符串转换为整数形式.　如，将字符串`'13531'`转换为整数`13531`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13531\n"
     ]
    }
   ],
   "source": [
    "from math import pow\n",
    "\n",
    "def str2num(string):\n",
    "    L=len(string);\n",
    "    if L==1:\n",
    "        return int(string[0]);\n",
    "    else:\n",
    "        return str2num(string[1:]) + int(pow(10,L-1)*int(string[0]));\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    string='13531';\n",
    "    print(str2num(string));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. 编写递归函数，计算$\\log_2 n$的整数部分． (要求：只使用加法和整数除法)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "def log2_n(n):\n",
    "    if n<2:\n",
    "        return 0\n",
    "    else:\n",
    "        return log2_n(n//2) + 1;\n",
    "\n",
    "if __name__=='__main__':\n",
    "    print(log2_n(5))\n",
    "    print(log2_n(59))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. 编写递归函数，计算两个正整数`m`和`n`的乘积.  (要求：只能使用加法和减法)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'\\n之所以这样写是为了避免采用n个m相加的方法时碰到用n、m中较大的一个控制递归，\\n造成递归层数较多，以上算法总可以保证以n、m中较小的一个作为递归层数\\n'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def multiply(m,n):\n",
    "    if m==1 or n==1:\n",
    "        return m + n - 1;\n",
    "    else:\n",
    "        return multiply(m-1,n-1) + m + n - 1;\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    print(multiply(5,3));\n",
    "    \n",
    "'''\n",
    "之所以这样写是为了避免采用n个m相加的方法时碰到用n、m中较大的一个控制递归，\n",
    "造成递归层数较多，以上算法总可以保证以n、m中较小的一个作为递归层数\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. 编写递归函数，输入字符串`s`，输出其翻转字符串．如，`'pots&pans'`翻转后为`'snap&stop'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "olleh\n",
      "snap&stop\n"
     ]
    }
   ],
   "source": [
    "def reverse(s):\n",
    "    if s == '':\n",
    "        return s;\n",
    "    else:\n",
    "        return reverse(s[1:]) + s[0];\n",
    "\n",
    "if __name__=='__main__':\n",
    "    print(reverse('hello'));\n",
    "    print(reverse('pots&pans'));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. 编写一个递归函数，判断某个字符串`'s'`是否为为回文结构．所谓＂回文＂，即顺读和倒读都一样的字符串．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def palindrome(string):\n",
    "    if len(string)<2:\n",
    "        return True;\n",
    "    else:\n",
    "        return palindrome(string[1:-1]) and (string[0]==string[-1])\n",
    "\n",
    "if __name__=='__main__':\n",
    "    print(palindrome('abcdcba'));\n",
    "    print(palindrome('abcdeba'));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8. 编写一个函数头为`find(path, filename)`的递归函数，报告以给定路径`path`为根的文件系统的名为`filename`的所有条目．"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d:/test\\Child1\\target.txt\n",
      "d:/test\\Child2\\ChildOfChild\\target.txt\n",
      "d:/test\\Child2\\target.txt\n",
      "d:/test\\target.txt\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import shutil\n",
    "\n",
    "def findTargetFile(path,filename):\n",
    "    if os.path.isdir(path):\n",
    "        for name in os.listdir(path):\n",
    "            childpath=os.path.join(path,name);\n",
    "            if name==filename:\n",
    "                print(childpath);\n",
    "            findTargetFile(childpath,filename);\n",
    "    return;\n",
    "    \n",
    "if __name__=='__main__':\n",
    "    #创建测试文件夹\n",
    "    os.makedirs('d:/test/Child2/ChildOfChild')\n",
    "    os.makedirs('d:/test/Child1')\n",
    "    file = open('d:/test/target.txt','w');file.close()\n",
    "    file = open('d:/test/2.txt','w');file.close()\n",
    "    file = open('d:/test/Child1/target.txt','w');file.close()\n",
    "    file = open('d:/test/Child2/target.txt','w');file.close()\n",
    "    file = open('d:/test/Child2/2.txt','w');file.close()\n",
    "    file = open('d:/test/Child2/ChildOfChild/target.txt','w');file.close()\n",
    "    #测试函数\n",
    "    findTargetFile('d:/test','target.txt');\n",
    "    #删除测试文件夹\n",
    "    shutil.rmtree('d:/test');"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
